/* 63. 不同路径 II */
/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function (obstacleGrid) {
    const row = obstacleGrid.length, col = obstacleGrid[0].length
    const dp = new Array(row).fill(0).map(() => new Array(col).fill(0))
    /* 前面都没有路后面也没有路 */
    let rowFlag = false, colFlag = false
    for (let i = 0; i < row; i++) {
        if (obstacleGrid[i][0]) {
            dp[i][0] = 0
            rowFlag = true
        } else {
            dp[i][0] = rowFlag ? 0 : 1
        }
    }

    for (let i = 1; i < col; i++) {
        if (obstacleGrid[0][i]) {
            dp[0][i] = 0
            colFlag = true
        } else {
            dp[0][i] = colFlag ? 0 : 1
        }
    }

    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            if (obstacleGrid[i][j]) {
                dp[i][j] = 0
            } else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
    }
    return dp[0][0] ? dp[row - 1][col - 1] : 0
};
var uniquePathsWithObstacles = function (obstacleGrid) {
    const n = obstacleGrid.length, m = obstacleGrid[0].length
    const dp = new Array(m).fill(0)
    dp[0] = !obstacleGrid[0][0] ? 1 : 0

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (obstacleGrid[i][j]) {
                dp[j] = 0
                continue
            }
            if (j && !obstacleGrid[i][j - 1]) {
                dp[j] += dp[j - 1]
            }
        }
    }
    return dp[m - 1]
}
const result = uniquePathsWithObstacles([[0, 0], [1, 1], [0, 0]])
console.log('result :>>', result);